Sorting and switching networks are widely used as interconnection networks in telecommunications, parallel computing, and distributed computing.
There is a renewed interest in these networks in Asynchronous Transfer Mode (ATM) technology. ATM switches are commonly used in telecommunication networks to switch voice, data, and video. ATM switches deploy various sorting and switching networks to receive incoming packets and sort them according to destination.
In a typical ATM switch, these sorting and switching networks are systematically laid on a VLSI chip. However, the layouts of these sorting networks on VLSI chips have always been a problem. The sorting networks have connections which are angled in three dimensional space; wherein VLSI chips use a two dimensional grid-model comprising only horizontal rows and vertical columns. In this grid-model, various sorters and other network nodes are mapped to a subset of grid points, and the connections between the nodes are selected using the edge-disjoint wiring along grid rows and grid columns.
Therefore, there exists a need for an improved systematic method for laying out these sorting networks on VLSI chips. The goal is to produce an area-efficient layout. The production cost of a VLSI chip grows with the total area of its layout, and it is desirable to produce a layout of sorting networks on VLSI chips as compactly as possible.